package myself.a008CodingTest;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/25
 * Time 21:49
 * Mail 739153436@qq.com
 */
public class CopySpecialList {

    // 笔试用
    public static Node copyListWithRand1(Node head) {
        if (head == null) {
            return null;
        }
        // 准备拷贝节点
        Map<Node, Node> copyMap = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            copyMap.put(cur, new Node(cur.value));
            cur = cur.next;
        }

        // 二次遍历进行节点复制
        cur = head;
        while (cur != null) {
            // next 节点连接
            copyMap.get(cur).next = copyMap.get(cur.next);

            // rand 节点连接
            copyMap.get(cur).rand = copyMap.get(cur.rand);

            cur = cur.next;
        }
        return copyMap.get(head);
    }

    // 面试用
    public static Node copyListWithRand2(Node head) {
        if (head == null) {
            return null;
        }
        // 准备复制节点
        Node cur = head;

        while (cur != null) {
            Node copy = new Node(cur.value);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next;
        }
        // 遍历进行新节点rand指针设置
        cur = head;

        while (cur != null) {
            cur.next.rand = cur.rand != null ? cur.rand.next : null;
            cur = cur.next.next;
        }

        // 原链表复原，新的复制链表生成
        cur = head;
        Node result = head.next;
        while (cur != null) {
            Node next = cur.next.next;
            Node copy = cur.next;
            copy.next = next != null ? next.next : null;
            cur.next = next;
            cur = next;
        }
        return result;
    }

    public static class Node {
        public int value;
        public Node next;
        public Node rand;

        public Node(int data) {
            this.value = data;
        }
    }
}
